package dfs;


import java.util.ArrayList;
import java.util.List;

/**
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 * https://leetcode-cn.com/problems/permutation-i-lcci/
 *
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/14 17:58
 */
public class Permutation {
    public static void main(String[] args) {
        String[] strings = permutation("qwe");
        for (String s : strings) {
            System.out.println(s);
        }

    }

    public static String[] permutation(String S) {
        char[] chars = S.toCharArray();
        List<String> strs = new ArrayList<>();
        backtracking(1, chars, "", new int[chars.length], strs);
        return strs.toArray(new String[0]);
    }

    private static void backtracking(int t, char[] chars, String str, int[] strack, List<String> strs) {

        int len = chars.length;
        if (t > len) {
            strs.add(str);
        } else {
            for (int i = 0; i < len; i++) {
                if (strack[i] == 0) {
                    strack[i] = 1;
                    backtracking(++t, chars, str + chars[i], strack, strs);//进入下一层
                    //回溯
                    --t;
                    strack[i] = 0;
                }
            }
        }


    }
}
